Digitally stored electronic maps are used to provide directions to users of mobile devices, for example, using any of a wide array of standalone map or direction application programs or apps. Today's electronic maps correctly determine where a mobile device is within a few feet or meters, or show where the user of that mobile device is on the electronic map in real time. Electronic maps also typically include other functionality, such as providing turn-by-turn directions to nearly any location. Additional elements such as traffic or wrecks may also be shown.
Electronic maps also appear in other applications aside from standalone mapping applications. For example, ride sharing applications, taxi applications, video games, and other applications may use digital maps. These or other applications can obtain electronic maps by calling a map server computer through an Application Programming Interface (API). Thus, a single electronic map provider that owns or operates the server computer may supply the electronic maps for many different applications.
The electronic map provider may store electronic map data for the many different map applications. However, not all applications require the same set of data. Each application may only use a portion of electronic map data it receives. Sending unnecessary map data is an inefficient use of device memory and network bandwidth, but storing a separate set of map data for each application requires a large amount of storage. Data links between a mobile computing device and server computer may have low bandwidth or high cost, as in the case of some cellular radiotelephone data links. Thus, improved methods for providing electronic map data are needed.
Electronic maps include polygon regions, such as buildings, regions of land, or bodies of water. It is useful to provide labels for these shapes at or near a visual center. A visual center can be a perceived center of a polygon, such as a point at or near the center of a large area of the polygon. Some conventional methods for estimating a visual center of a polygon are error prone, especially for irregularly shaped polygons. For example, calculating a polygon's centroid has been used to estimate its visual center. While calculating a centroid is relatively simple and fast, it does not always find a suitable visual center. For example, for concave polygons, the centroid can fall outside the borders of the polygon, which is not a suitable estimate of a visible center.
Other known methods find an exact visual center of a polygon, which is referred to as a pole of inaccessibility. The pole of inaccessibility is the center of the largest circle that can be inscribed within the polygon (i.e., the largest inscribed circle). The pole of inaccessibility is also the point inside the polygon that is most distant from the border of the polygon. Prior methods for finding the pole of inaccessibility involve performing constrained Delaunay Triangulation or calculating straight skeleton. Both of these methods are slow and computationally expensive. Garcia-Castellanos and Lombardo provided an algorithm for approximating the pole of inaccessibility that involves repeatedly probing a polygon with points on a grid. However, their algorithm is slow on large polygons, and it is not guaranteed to accurately approximate the visual center for irregular polygons.